#include <bits/stdc++.h>

using namespace std;

// 买卖股票的最佳时机 IV
// 给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格
// 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易
// 也就是说，你最多可以买 k 次，卖 k 次
// 注意：你不能同时参与多笔交易，你必须在再次购买前出售掉之前的股票
// 测试链接 : https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/

class Solution 
{
public:
    int free(vector<int>& prices)
    {
        int ans = 0;
        for(int i = 1; i < prices.size(); ++i)
        {
            ans += max(prices[i] - prices[i - 1], 0);
        }
        return ans;
    }

    int maxProfit1(int k, vector<int>& prices) 
    {
        int n = prices.size();
        if(k >= n / 2)
        {
            // 这是一个剪枝
			// 如果k >= n / 2，那么代表所有上坡都可以抓到
			// 所有上坡都可以抓到 == 交易次数无限，所以回到股票问题2
            return free(prices);
        }
        // dp[i][j] : 从第0天到第j天，完成了i笔交易时的最大利润
        int dp[k + 1][n];
        memset(dp, 0, sizeof dp);
        // dp[...][0] : 0，在第0天完成多笔交易，最大利润为0
        // dp[0][...] : 0，完成0笔交易，最大利润为0
        for(int i = 1; i <= k; ++i)
        {
            // 第j天卖出股票
            for(int j = 1; j < n; ++j)
            {
                dp[i][j] = dp[i][j - 1]; // 延续前一天的状态
                // 第p天买入第i笔交易的股票
                for(int p = 0; p < j; ++p)
                {
                    dp[i][j] = max(dp[i][j], dp[i - 1][p] + prices[j] - prices[p]);
                }
            }
        }        
        return dp[k][n - 1];
    }

    int maxProfit2(int k, vector<int>& prices) 
    {
        int n = prices.size();
        if(k >= n / 2)
        {
            // 这是一个剪枝
			// 如果k >= n / 2，那么代表所有上坡都可以抓到
			// 所有上坡都可以抓到 == 交易次数无限，所以回到股票问题2
            return free(prices);
        }
        // dp[i][j] : 从第0天到第j天，完成了i笔交易时的最大利润
        int dp[k + 1][n];
        memset(dp, 0, sizeof dp);
        // dp[...][0] : 0，在第0天完成多笔交易，最大利润为0
        // dp[0][...] : 0，完成0笔交易，最大利润为0
        for(int i = 1, best; i <= k; ++i)
        {
            best = dp[i - 1][0] - prices[0];
            // 第j天卖出股票
            for(int j = 1; j < n; ++j)
            {
                // 用best变量替代了枚举行为
                dp[i][j] = max(dp[i][j - 1], best + prices[j]);
                best = max(best, dp[i - 1][j] - prices[j]);
            }
        }        
        return dp[k][n - 1];
    }

    // 对方法2进行空间压缩的版本
    int maxProfit(int k, vector<int>& prices) 
    {
        int n = prices.size();
        if(k >= n / 2)
        {
            // 这是一个剪枝
			// 如果k >= n / 2，那么代表所有上坡都可以抓到
			// 所有上坡都可以抓到 == 交易次数无限，所以回到股票问题2
            return free(prices);
        }
        int dp[n];
        memset(dp, 0, sizeof dp);
        for(int i = 1, best, tmp; i <= k; ++i)
        {
            best = dp[0] - prices[0];
            // 第j天卖出股票
            for(int j = 1; j < n; ++j)
            {
                tmp = dp[j];
                dp[j] = max(dp[j - 1], best + prices[j]);
                best = max(best, tmp - prices[j]);
            }
        }        
        return dp[n - 1];
    }
};


class Solution 
{
public:
    int maxProfit(int k, vector<int>& prices) 
    {
        int n = prices.size();
        k = min(k, n / 2);
        // f[i][j] : 从0到i天范围内，进行了j次交易且持有股票时的最大利润
        // g[i][j] : 从0到i天范围内，进行了j次交易且不持有股票时的最大利润
        // 注意：将股票卖出才能够算作一次交易
        int f[n][k + 1], g[n][k + 1];
        memset(f, -0x3f, sizeof f);
        memcpy(g, f, sizeof f);
        f[0][0] = -prices[0], g[0][0] = 0;
        for(int i = 1; i < n; ++i)
        {
            for(int j = 0; j <= k; ++j)
            {
                // f[i - 1][j] ：延续前一天的状态
                // g[i - 1][j] - prices[i] : 第i天买入股票，则第i天持有股票
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                // g[i - 1][j] ：延续前一天的状态
                g[i][j] = g[i - 1][j];
                if(j >= 1)
                {
                    // f[i - 1][j - 1] + prices[i] ：第i天卖出股票，完成一笔交易
                    g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
                }
            }
        }

        int ret = 0;
        for(int j = 0; j <= k; ++j)
        {
            ret = max(ret, g[n - 1][j]);
        }
        return ret;
    }
};